/**
 * 寻找两个有序数组的中位数
 * 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
 * <p>
 * 请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
 * <p>
 * O(log(m + n))表示是两分法，如果是从头开始遍历的复杂度是O(m + n)
 */
class FindMedianSortedArrays {

    public static void main(String[] args) {
        //int[] nums1 = {1, 3, 7, 10};
        //int[] nums2 = {2, 4, 8, 10, 12, 14, 18, 20};
        //int[] nums1 = {1, 2, 3, 4};
        //int[] nums2 = {5, 6, 7, 8, 9, 10, 11, 12, 13};
        //int[] nums1 = {91, 92, 93, 94};
        //int[] nums2 = {5, 6, 7, 8, 9, 10, 11, 12, 13};
        int[] nums1 = {};
        int[] nums2 = {2, 3, 4, 5, 6, 7, 8};
        System.out.println(FindMedianSortedArrays.findMedianSortedArrays(nums1, nums2));
    }

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int all = nums1.length + nums2.length;
        //wanted表示需要找的位数，如果all是奇数，主要找的是all/2这个数；如果all是偶数，则需要找的是all/2和all/2+1两个数的平均数
        int wanted = all / 2;
        //是否需要仅仅一个值
        boolean ifOne = false;
        if (all % 2 != 0) {
            ifOne = true;
            wanted += 1;
        }
        //remove表示每次需要移除的数量
        int remove;
        //remove1表示数组1已经移除的数量
        int remove1 = 0;
        //remove1表示数组1已经移除的数量
        int remove2 = 0;
        double value = 0;

        while (wanted != 1) {
            remove = wanted / 2;
            //根据remove得出需要比较的两个子数组
            //如果已经有数组为空，则直接算出答案
            if (remove1 == nums1.length) {
                if (ifOne) {
                    value = nums2[remove2 + wanted - 1];
                } else {
                    value = (double) (nums2[remove2 + wanted - 1] + nums2[remove2 + wanted]) / 2;
                }
                break;
            } else if (remove2 == nums2.length) {
                if (ifOne) {
                    value = nums1[remove1 + wanted - 1];
                } else {
                    value = (double) (nums1[remove1 + wanted - 1] + nums1[remove1 + wanted]) / 2;
                }
                break;
            }
            //先判断边界
            if (remove1 + remove >= nums1.length) {
                if (nums1[nums1.length - 1] <= nums2[remove2 + remove - 1]) {
                    //移除num1中多余的部分
                    wanted -= nums1.length - remove1;
                    remove1 = nums1.length;
                } else {
                    remove2 += remove;
                    wanted -= remove;
                }
            } else if (remove2 + remove >= nums2.length) {
                if (nums2[nums2.length - 1] <= nums1[remove1 + remove - 1]) {
                    //移除num2中多余的部分
                    wanted -= nums2.length - remove2;
                    remove2 = nums2.length;
                } else {
                    remove1 += remove;
                    wanted -= remove;
                }
            } else {
                if (nums1[remove1 + remove - 1] <= nums2[remove2 + remove - 1]) {
                    //移除num1中多余的部分
                    remove1 += remove;
                } else {
                    remove2 += remove;
                }
                wanted -= remove;
            }
        }

        //如果已经有数组为空，则直接算出答案
        if (wanted != 1) {
            return value;
        }

        if (ifOne) {
            //如果是奇数，找两个剩余数组的开头最小值
            if (remove1 == nums1.length) {
                return nums2[remove2];
            } else if (remove2 == nums2.length) {
                return nums1[remove1];
            } else {
                return min(nums1[remove1], nums2[remove2]);
            }
        } else {
            //如果是偶数，找两个剩余数组的前两个值
            if (remove1 == nums1.length) {
                return (double) (nums2[remove2] + nums2[remove2 + 1]) / 2;
            } else if (remove2 == nums2.length) {
                return (double) (nums1[remove1] + nums1[remove1 + 1]) / 2;
            } else {
                int value1 = 0, value2 = 0;
                if (nums1[remove1] <= nums2[remove2]) {
                    value1 = nums1[remove1];
                    if (remove1 == nums1.length - 1) {
                        //如果已经是最后一个数组了
                        value2 = nums2[remove2];
                    } else {
                        value2 = min(nums1[remove1 + 1], nums2[remove2]);
                    }
                } else {
                    value1 = nums2[remove2];
                    if (remove2 == nums2.length - 1) {
                        //如果已经是最后一个数组了
                        value2 = nums1[remove1];
                    } else {
                        value2 = min(nums1[remove1], nums2[remove2 + 1]);
                    }
                }
                return (double) (value1 + value2) / 2;
            }
        }

    }

    public static int min(int a, int b) {
        if (a <= b) {
            return a;
        } else {
            return b;
        }
    }

}